{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Time For K Virus Variants to Spread"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #array #math #binary-search #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数组 #数学 #二分查找 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minDayskVariants"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #感染 K 种病毒所需的最短时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在无限大的二维平面上有&nbsp;<code>n</code>&nbsp;种 <strong>不同</strong> 的病毒。给定二维数组&nbsp;<code>points</code>&nbsp;，<span style=\"\">第 </span><code>i</code><span style=\"\"> 项&nbsp;</span><code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code>&nbsp;说明第&nbsp;<code>0</code>&nbsp;天有一种病毒在点&nbsp;<code>(x<sub>i</sub>, y<sub>i</sub>)</code>&nbsp;。注意初始状态下，可能有 <strong>多种</strong> 病毒在 <strong>同一点</strong> 上。</p>\n",
    "\n",
    "<p>每天，被感染的点会把它感染的病毒传播到上、下、左、右四个邻居点。</p>\n",
    "\n",
    "<p>现给定一个整数 <code>k</code>&nbsp;，问 <strong>最少</strong> 需要多少天，方能找到一点感染 <strong>至少</strong> <code>k</code> 种病毒？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/30/case-1.png\" style=\"width: 421px; height: 256px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[1,1],[6,1]], k = 2\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>在第 3 天，点 (3,1) 与 (4,1) 将感染所有 2 种病毒。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/30/case-2.png\" style=\"width: 416px; height: 257px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[3,3],[1,2],[9,2]], k = 2\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>在第 2 天, 点 (1,2), (1,3), (2,1), (2,2), (3,1) 和 (3,3) 将会感染前两种病毒。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/30/case-2.png\" style=\"width: 416px; height: 257px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>points = [[3,3],[1,2],[9,2]], k = 3\n",
    "<b>输出：</b>4\n",
    "<strong>解释：</strong>在第 4 天，点 (5,2) 会感染所有 3 种病毒。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == points.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 50</code></li>\n",
    "\t<li><code>points[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>2 &lt;= k &lt;= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-time-for-k-virus-variants-to-spread](https://leetcode.cn/problems/minimum-time-for-k-virus-variants-to-spread/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-time-for-k-virus-variants-to-spread](https://leetcode.cn/problems/minimum-time-for-k-virus-variants-to-spread/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1],[6,1]]\\n2', '[[3,3],[1,2],[9,2]]\\n2', '[[3,3],[1,2],[9,2]]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDayskVariants(self, points: List[List[int]], k: int) -> int:\n",
    "        def check(t):\n",
    "            sl,i = SortedList(),0\n",
    "            for x,y in A:\n",
    "                sl.add(y)\n",
    "                while x-A[i][0]>2*t:\n",
    "                    sl.remove(A[i][1])\n",
    "                    i += 1\n",
    "                for j in range(k-1,len(sl)):\n",
    "                    if x-A[i][0]==sl[j]-sl[j-k+1]==2*t and (x+sl[j])%2:\n",
    "                        continue\n",
    "                    if sl[j]-sl[j-k+1]<=2*t:\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        from sortedcontainers import SortedList\n",
    "        A = sorted((y+x,y-x) for x,y in points)\n",
    "        ma = max(p[0] for p in A)\n",
    "        return bisect_left(range(ma),True,key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDayskVariants(self, points: List[List[int]], k: int) -> int:\n",
    "        def check(t):\n",
    "            sl,i = SortedList(),0\n",
    "            for x,y in A:\n",
    "                sl.add(y)\n",
    "                while x-A[i][0]>2*t:\n",
    "                    sl.remove(A[i][1])\n",
    "                    i += 1\n",
    "                for j in range(k-1,len(sl)):\n",
    "                    if sl[j]-sl[j-k+1]<=2*t and not (x-A[i][0]==sl[j]-sl[j-k+1]==2*t and (x+sl[j])%2):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        from sortedcontainers import SortedList\n",
    "        A = sorted((y+x,y-x) for x,y in points)\n",
    "        ma = max(p[0] for p in A)\n",
    "        return bisect_left(range(ma),True,key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDayskVariants(self, points: List[List[int]], k: int) -> int:\n",
    "        def check(t):\n",
    "            sl,i = SortedList(),0\n",
    "            for x,y in A:\n",
    "                sl.add(y)\n",
    "                while x-A[i][0]>2*t:\n",
    "                    sl.remove(A[i][1])\n",
    "                    i += 1\n",
    "                for j in range(k-1,len(sl)):\n",
    "                    if sl[j]-sl[j-k+1]<=2*t and not (x-A[i][0]==sl[j]-sl[j-k+1]==2*t and (x+sl[j-k+1])%2):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        from sortedcontainers import SortedList\n",
    "        A = sorted((y+x,y-x) for x,y in points)\n",
    "        ma = max(p[0] for p in A)\n",
    "        return bisect_left(range(ma),True,key=check)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
